import org.junit.Test;

import java.util.LinkedList;

/**
 * 判断是否为合法的二叉搜索树
 * @author liuzhaoqiang
 */
public class E04Leetcode98 {
    /**
     * 使用非递归的方式实现
     * 使用中序遍历二叉搜索树，中序遍历的结果是升序的
     * 判断上一个值和当前节点比较 如果大于就是非标准的二叉搜索树
     *
     *                 4
     *                / \
     *               2   6
     *                  / \
     *                 3   7
     *
     * @param root
     * @return
     */
    public boolean isValidBTree(TreeNode root){
        LinkedList<TreeNode> stack = new LinkedList();
        TreeNode p = root;
        long prev = Long.MIN_VALUE;
        while(p!=null || !stack.isEmpty()){
            if(p!=null){
                stack.push(p);
                p = p.left;
            }else{
                TreeNode pop = stack.pop();
                if(prev>=pop.val){
                    return false;
                }
                prev = pop.val;
                p = pop.right;
            }
        }
        return true;
    }

    /**
     * 给每个节点添加上限和下限 如果当前节点的值不在这个上限和下限的范围内 就不是一个合法的二叉搜索树
     * 递归调用 后面的节点的上下限和父节点的值有关
     * @param node
     * @return
     */
    public boolean isValidBTree2(TreeNode node){
        return isValidBTree2(node, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValidBTree2(TreeNode node, long min,long max){
        if(node == null){
            return true;
        }
        if(node.val<=min || node.val>=max){
            return false;
        }
        return isValidBTree2(node.left, min, node.val) && isValidBTree2(node.right, node.val, max);
    }
    @Test
    public void test(){
        /*
                4
               / \
              2   6
             / \
            1   3
        */
        TreeNode root1 = new TreeNode(4, new TreeNode(2, new TreeNode(1), new TreeNode(3)), new TreeNode(6));
        System.out.println(new E04Leetcode98().isValidBTree(root1));
        System.out.println("---------------");
    }

    public static void main(String[] args) {

        /*
                4
               / \
              2   6
                 / \
                3   7
         */
        TreeNode root2 = new TreeNode(4, new TreeNode(2), new TreeNode(6, new TreeNode(3), new TreeNode(7)));
        System.out.println(new E04Leetcode98().isValidBTree(root2));
//        System.out.println("---------------");

        /*
               1
              /
             1
         */
        TreeNode root3 = new TreeNode(1, new TreeNode(1), null);
        System.out.println(new E04Leetcode98().isValidBTree(root3));
//        System.out.println("---------------");

        /*
              3
               \
                4
               /
              5
         */
        TreeNode root4 = new TreeNode(3, null, new TreeNode(4, new TreeNode(5), null));
        System.out.println(new E04Leetcode98().isValidBTree(root4));
    }



    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
